/*
 * @lc app=leetcode.cn id=1987 lang=cpp
 *
 * [1987] 不同的好子序列数目
 */

// @lc code=start
class Solution
{
public:
    int numberOfUniqueGoodSubsequences(string binary)
    {
        int n = binary.size(), mod_num = (int)(1e9 + 7);
        int f[n + 1][2], flag = 0;
        f[n][0] = f[n][1] = 0;

        for (int i = n - 1; i >= 0; i--)
        {
            if (binary[i] == '0')
            {
                flag = 1;
                f[i][0] = f[i + 1][0] + f[i + 1][1] + 1;
                f[i][1] = f[i + 1][1];
            }
            else
            {
                f[i][1] = f[i + 1][0] + f[i + 1][1] + 1;
                f[i][0] = f[i + 1][0];
            }
            f[i][0] %= mod_num;
            f[i][1] %= mod_num;
        }

        return f[0][1] + flag;
    }
};
// @lc code=end
